package com.lun.medium;

import java.util.ArrayList;
import java.util.List;

public class PalindromePartitioning {
	
	public List<List<String>> partition(String s) {
		List<String> path = new ArrayList<>();
		List<List<String>> result = new ArrayList<>();
		backtracking(path, s, 0, result);
		return result;
	}
	
	private void backtracking(List<String> path, String originalString, // 
			int startIndex, List<List<String>> result) {
		
		if(startIndex >= originalString.length()) {
			result.add(new ArrayList<>(path));
			return;
		}
		
		for(int i = startIndex + 1; i <= originalString.length(); i++) {
			
			if(isPalindrome(originalString, startIndex, i)) {
				path.add(originalString.substring(startIndex, i));
			}else {
				continue;
			}
			
			backtracking(path, originalString, i, result);
			path.remove(path.size() - 1);
		}
		
	}
	
	private boolean isPalindrome(String str, int startIndex, int endIndex) {
		for(endIndex--; startIndex < endIndex; startIndex++, endIndex--) {
			if(str.charAt(startIndex) != str.charAt(endIndex))
				return false;
		}
		return true;
	}
	
}
